package net.cyndeline.scalarlib.rlgraph.regularEdgeLabeling.altFourCycles

import scala.reflect.runtime.universe.TypeTag
import scala.reflect.ClassTag
import net.cyndeline.scalarlib.rlgraph.regularEdgeLabeling.angularMap.{AngularVertex, AngularMap}
import net.cyndeline.scalarlib.rlgraph.regularEdgeLabeling.{LabelEdge, EdgeLabeling}
import net.cyndeline.scalarlib.rlgraph.face.FaceComputation
import scala.collection.mutable.ListBuffer
import net.cyndeline.scalarlib.rlgraph.cycles.{DirectedCycleFinder, CycleFinder, Cycle}
import scalax.collection.immutable.Graph
import scalax.collection.GraphEdge.DiEdge
import scalax.collection.GraphPredef._
import net.cyndeline.scalarlib.util.UnorderedPair
import scala.collection.mutable

/**
 * For a more in-depth study of alternating 4-cycles and their applications in REL combinatorics, see the thesis
 * "Combinatoire des cartes planaires et applications algorithmiques" by Eric Fusy (there referred to as transversal
 * structures).
 *
 * This class computes the essential clockwise circuits of a planar embedding with a regular edge labeling attached
 * to it. An alternating 4-cycle is such a circuit where every edge in the cycle alternates between the sets T1 and T2.
 * Flipping a cycle means changing the set (from T1 to T2 or vice versa) for each edge present inside the cycle
 * (but not on it).
 *
 * An alternating 4-cycle can either be left- or right alternating. A left alternating cycle is one where the interior
 * edges of the cycle C connected to a vertex V on the cycle belongs to the same set (T1/T2) as the cycle-edge to the
 * left of them. A right alternating cycle is the same but for the right cycle-edge of V.
 *
 * @param regularEdgeLabeling The edge labeling that represents the current edge orientations of the 4-cycles in this
 *                            collection.
 * @param allCycles Every essential alternating 4-cycle in the regular edge labeling.
 */
class AlternatingFourCycles[V : TypeTag : ClassTag] private (val regularEdgeLabeling: EdgeLabeling[V],
                                                             val allCycles: Vector[FourCycle[V]]) {

  /**
   * Changes the T-set membership for every interior edge in the 4-cycle collection, and updates the regular edge
   * labeling associated with it.
   * @param c Cycle to flip.
   * @return A new 4-cycle collection with the cycle flipped.
   */
  def flipCycle(c: FourCycle[V]): AlternatingFourCycles[V] = {
    val index = c match {
      case ck: EssentialFourCycle[V] => ck.index
    }
    require(allCycles.isDefinedAt(index), "The supplied cycle " + c + " it not defined in this 4-cycle collection.")
    val edgeLabeling = regularEdgeLabeling.flipEdges(c.innerEdges)
    new AlternatingFourCycles(edgeLabeling, allCycles.updated(index, c.flip))
  }

}

/**
 * Factory object used to instantiate an initial four cycle collection.
 */
object AlternatingFourCycles {

  /**
   * @param rel A regular edge labeling to parse all essential alternating 4-cycles from.
   * @tparam V Vertex type in the edge labeling.
   * @return A collection of every essential alternating 4-cycle in the labeling.
   */
  def apply[V : TypeTag : ClassTag](rel: EdgeLabeling[V]) = {
    val angles = new AngularMap(rel)
    val cycleValidation = new CycleVerifier()
    val faceCycles = computeRectangularFaceCycles(angles, 0, cycleValidation, rel)
    val allCycles = faceCycles ++ computeEightCycles(angles, faceCycles.size, cycleValidation, rel)

    new AlternatingFourCycles(rel, allCycles)
  }

  private def computeRectangularFaceCycles[V : TypeTag : ClassTag](map: AngularMap[V],
                                                                  startId: Int,
                                                                  cycleValidation: CycleVerifier,
                                                                  rel: EdgeLabeling[V]): Vector[FourCycle[V]] = {
    val faces = new FaceComputation[AngularVertex[V]]().computeFaces(map.angularEmbedding).filter(_.vertexSize == 4)
    val validFourCycles = new ListBuffer[FourCycle[V]]()
    var nextAvailableIndex = startId

    for (f <- faces) {
      val blackVertices = f.vertices.filter(_.isBlack)
      val validCycle: Option[Cycle[AngularVertex[V]]] = if (cycleValidation.verifyFaceCycle(f.cycle, map))
        Some(f.cycle)
      else if (cycleValidation.verifyFaceCycle(f.cycle.reverse, map)) {
        Some(f.cycle.reverse)
      } else {
        None
      }

      if (validCycle.isDefined) {
        val cycle = validCycle.get.vertices
        val centerEdge = findCenterEdge(blackVertices(0).vertex, blackVertices(1).vertex, rel)
        val blackWhitePairs = cycle zip (cycle.drop(1) :+ cycle.head) // Alternates between B/W and W/B
        val outerRelEdges = ListBuffer[LabelEdge[V]]()

        for (bw <- blackWhitePairs) {
          val black = if (bw._1.isBlack) bw._1 else bw._2
          val secondBlack = blackVertices.find(_ != black).get
          outerRelEdges += findOuterFaceEdge(bw._1, bw._2, secondBlack, map, rel)
        }

        validFourCycles += EssentialFourCycle(outerRelEdges.toVector, Vector(centerEdge), nextAvailableIndex, rel)
        nextAvailableIndex += 1
      }
    }

    validFourCycles.toVector
  }

  private def computeEightCycles[V : TypeTag : ClassTag](map: AngularMap[V],
                                                        startIndex: Int,
                                                        cycleValidation: CycleVerifier,
                                                        rel: EdgeLabeling[V]): Vector[FourCycle[V]] = {
    val cycleFinder: CycleFinder[AngularVertex[V], DiEdge] = new DirectedCycleFinder()
    val allCycles = cycleFinder.findCycles(angularMapToDirected(map)).filter(_.length == 8)
    var nextAvailableIndex = startIndex
    val validFourCycles = new ListBuffer[FourCycle[V]]()

    for (c <- allCycles) {
      val validCycle = if (cycleValidation.verifyEightCycle(c, map)) {
        Some(c)
      } else if (cycleValidation.verifyEightCycle(c.reverse, map)) {
        Some(c.reverse)
      } else {
        None
      }

      if (validCycle.isDefined) {
        val cycle = validCycle.get
        val blackVertices = cycle.vertices.filter(_.isBlack) // The vertices of the cycle in the REL in the order they appear
        val edges = blackVertices.zip(blackVertices.drop(1) :+ blackVertices.head)
        val originalEdges = edges.map(e => (e._1.vertex, e._2.vertex))
        val outerEdges = findRELEdges(originalEdges, rel)
        val innerEdges = parseInnerEdges(originalEdges, blackVertices.map(_.vertex).toSet, rel)

        validFourCycles += EssentialFourCycle(outerEdges, innerEdges, nextAvailableIndex, rel)
        nextAvailableIndex += 1
      }
    }


    validFourCycles.toVector
  }

  /*
   * Rectangular face help methods
   */

  /**
   * @param from A white or black vertex in the quadrangular face.
   * @param to The next black (white) vertex if 'from is white (black).
   * @param secondBlack Given a W/B edge, this is the second black vertex in the face.
   * @return The edge in the 4-cycle that is connected to the third edge of the white vertex.
   */
  private def findOuterFaceEdge[V](from: AngularVertex[V],
                                  to: AngularVertex[V],
                                  secondBlack: AngularVertex[V],
                                  map: AngularMap[V],
                                  rel: EdgeLabeling[V]): LabelEdge[V] = {
    require(from.isBlack != to.isBlack, "A white and a black vertex is needed to infer the outer edge on a quadrangular angular face.")
    val white = if (from.isWhite) from else to
    val black = if (from.isBlack) from else to
    val thirdBlack = map.angularEmbedding.neighborsOf(white).find(n => n != black && n != secondBlack).get

    /* There's no way to tell if the black vertex should be first or last in the edge, it differs depending on
     * weather the current angular edge is moving against or along the directed REL edges.
     */
    val blackPair = Set(black.vertex, thirdBlack.vertex)
    rel.edges.find(e => Set(e.from, e.to) == blackPair).get
  }

  private def findCenterEdge[V](from: V, to: V, rel: EdgeLabeling[V]): LabelEdge[V] = rel.edges.find(e => Set(e.from, e.to) == Set(from, to)).getOrElse {
    throw new NoSuchElementException("Could not find an inner edge " + from + " to " + to + ".")
  }

  /*
   * Eight-cycle help methods
   */

  private def angularMapToDirected[V : TypeTag : ClassTag](map: AngularMap[V]): Graph[AngularVertex[V], DiEdge] = {
    val edges = new ListBuffer[DiEdge[AngularVertex[V]]]()

    for (edge <- map.angularEmbedding.edges) {
      val first = map.orientationOfEdge(edge._1, edge._2)
      val last = if (edge._1 == first) edge._2 else edge._1
      edges += first~>last
    }

    Graph.from(Nil, edges.toList)
  }

  private def findRELEdges[V](es: Vector[(V, V)], rel: EdgeLabeling[V]): Vector[LabelEdge[V]] = {
    val tupleSet = es.map(UnorderedPair(_)).toSet
    rel.edges.filter(e => tupleSet.contains(UnorderedPair(e.from, e.to)))
  }

  private def parseInnerEdges[V](edges: Vector[(V, V)], outer: Set[V], rel: EdgeLabeling[V]): Vector[LabelEdge[V]] = {
    val edgePairs = edges zip (edges.drop(1) :+ edges.head) // Needed to find inner clockwise vertices
    val embedding = rel.originalEmbedding

    //Start by finding a vertex whose clockwise neighbor isn't the vertex preceding it on the outer 4-cycle
    val start: ((V, V), (V, V)) = edgePairs.find(p => {
      val vertex = p._1._2
      val next = p._2._2
      val previous = p._1._1
      embedding.embeddingFor(vertex).entryFor(next).next.adjacentVertex != previous
    }).get
    val startNeighbor = embedding.embeddingFor(start._1._2).entryFor(start._2._2).next.adjacentVertex
    val processed = new mutable.HashSet[V]()
    val addedEdges = new mutable.HashSet[UnorderedPair[V]]()
    val unProcessed = new mutable.Queue[V]()
    unProcessed += startNeighbor

    val innerEdges = new ListBuffer[UnorderedPair[V]]()

    while (!unProcessed.isEmpty) {
      val next = unProcessed.dequeue()
      processed += next
      val neighbors = embedding
        .neighborsOf(next)
        .filter(!processed.contains(_))

      for (n <- neighbors) {
        val edge = UnorderedPair(next, n)
        if (!addedEdges.contains(edge)) {
          innerEdges += edge
          addedEdges += edge
        }

        // Edges connected to outer vertices will be added when the inner vertex is processed, so ignore the outer ones.
        if (!processed.contains(n) && !outer.contains(n)) {
          unProcessed enqueue n
        }
      }

      processed += next
    }


    findRELEdges(innerEdges.map(_.asTuple).toVector, rel)
  }
}
